package cn.icatw.leetcode.editor.cn;
//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：["()"]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
//
// Related Topics 字符串 动态规划 回溯 👍 3655 👎 0


import java.util.ArrayList;
import java.util.List;

//Java：括号生成
public class T22_GenerateParentheses {
    public static void main(String[] args) {
        Solution solution = new T22_GenerateParentheses().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> result = new ArrayList<>();
            dfs(result, n, n, "");
            return result;
        }

        private void dfs(List<String> result, int left, int right, String current) {
            //当左括号和右括号都用完时，添加到结果集
            if (left==0&&right==0){
                result.add(current);
                return;
            }
            //左括号剩余数量大于0时，添加左括号
            if (left>0){
                dfs(result, left-1, right, current+"(");
            }
            //右括号剩余数量大于左括号时，添加右括号
            if (right>left){
                dfs(result, left, right-1, current+")");
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
